#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 使用STL栈
void stackSTLDemo() {
    cout << "=== STL栈演示 ===" << endl;
    
    stack<int> st;
    
    // 入栈
    cout << "入栈操作:" << endl;
    st.push(1);
    cout << "入栈: 1" << endl;
    st.push(2);
    cout << "入栈: 2" << endl;
    st.push(3);
    cout << "入栈: 3" << endl;
    
    // 查看栈顶元素
    cout << "当前栈顶元素: " << st.top() << endl;
    
    // 出栈
    cout << "出栈操作:" << endl;
    st.pop();
    cout << "出栈后栈顶元素: " << st.top() << endl;
    
    // 栈大小
    cout << "当前栈大小: " << st.size() << endl;
    
    // 判断栈是否为空
    cout << "栈是否为空: " << (st.empty() ? "是" : "否") << endl;
    
    // 继续出栈
    st.pop();
    cout << "再次出栈后栈顶元素: " << st.top() << endl;
    st.pop();
    cout << "最后出栈后栈是否为空: " << (st.empty() ? "是" : "否") << endl;
}

// 自定义栈实现
class CustomStack {
private:
    int* arr;
    int capacity;
    int topIndex;

public:
    CustomStack(int size) {
        capacity = size;
        arr = new int[capacity];
        topIndex = -1;
    }
    
    ~CustomStack() {
        delete[] arr;
    }
    
    void push(int value) {
        if(topIndex >= capacity - 1) {
            cout << "栈已满! 无法入栈 " << value << endl;
            return;
        }
        arr[++topIndex] = value;
        cout << "入栈: " << value << endl;
    }
    
    void pop() {
        if(topIndex < 0) {
            cout << "栈为空! 无法出栈" << endl;
            return;
        }
        cout << "出栈: " << arr[topIndex] << endl;
        topIndex--;
    }
    
    int top() {
        if(topIndex < 0) {
            cout << "栈为空!" << endl;
            return -1;
        }
        return arr[topIndex];
    }
    
    bool empty() {
        return topIndex == -1;
    }
    
    int size() {
        return topIndex + 1;
    }
    
    void display() {
        if(empty()) {
            cout << "栈为空" << endl;
            return;
        }
        cout << "栈内容 (从底到顶): ";
        for(int i = 0; i <= topIndex; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

void customStackDemo() {
    cout << "\n=== 自定义栈演示 ===" << endl;
    
    CustomStack stack(5);
    
    cout << "初始状态: ";
    stack.display();
    
    // 入栈操作
    cout << "\n入栈操作:" << endl;
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.display();
    
    // 查看栈顶
    cout << "当前栈顶元素: " << stack.top() << endl;
    
    // 出栈操作
    cout << "\n出栈操作:" << endl;
    stack.pop();
    stack.display();
    
    cout << "当前栈顶元素: " << stack.top() << endl;
    
    // 继续操作
    stack.push(40);
    stack.push(50);
    stack.push(60); // 这会触发栈满警告
    stack.display();
}

// 栈的应用：括号匹配检查
bool isValidParentheses(const string& s) {
    cout << "\n=== 括号匹配检查演示 ===" << endl;
    cout << "检查字符串: \"" << s << "\"" << endl;
    
    stack<char> st;
    
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
            cout << "入栈: " << c << endl;
        } else if(c == ')' || c == ']' || c == '}') {
            if(st.empty()) {
                cout << "栈为空，无法匹配 " << c << endl;
                return false;
            }
            
            char top = st.top();
            cout << "栈顶: " << top << ", 当前字符: " << c << endl;
            
            if((c == ')' && top == '(') ||
               (c == ']' && top == '[') ||
               (c == '}' && top == '{')) {
                st.pop();
                cout << "匹配成功，出栈: " << top << endl;
            } else {
                cout << "匹配失败" << endl;
                return false;
            }
        }
    }
    
    bool result = st.empty();
    cout << "最终结果: " << (result ? "匹配成功" : "匹配失败") << endl;
    return result;
}

// 栈的应用：表达式求值（简单版本）
int evaluatePostfix(const string& expression) {
    cout << "\n=== 后缀表达式求值演示 ===" << endl;
    cout << "表达式: " << expression << endl;
    
    stack<int> st;
    
    for(char c : expression) {
        if(isdigit(c)) {
            st.push(c - '0');
            cout << "入栈: " << (c - '0') << endl;
        } else if(c == '+' || c == '-' || c == '*' || c == '/') {
            if(st.size() < 2) {
                cout << "操作数不足" << endl;
                return -1;
            }
            
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            int result;
            
            switch(c) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': result = a / b; break;
            }
            
            cout << "计算: " << a << " " << c << " " << b << " = " << result << endl;
            st.push(result);
        }
    }
    
    if(st.size() == 1) {
        cout << "最终结果: " << st.top() << endl;
        return st.top();
    } else {
        cout << "表达式格式错误" << endl;
        return -1;
    }
}

// ================ 竞赛常用写法 ================

// 竞赛推荐：STL stack的简洁写法
void stackContestDemo() {
    cout << "\n=== 竞赛常用：stack演示 ===" << endl;
    
    stack<int> st;
    
    // 简洁的入栈出栈
    for(int i = 1; i <= 5; i++) {
        st.push(i);
        cout << "入栈: " << i << endl;
    }
    
    cout << "栈顶元素: " << st.top() << endl;
    cout << "栈大小: " << st.size() << endl;
    
    // 清空栈
    while(!st.empty()) {
        cout << "出栈: " << st.top() << endl;
        st.pop();
    }
}

// 竞赛常用：用vector模拟栈
void vectorAsStackDemo() {
    cout << "\n=== 竞赛技巧：vector模拟栈 ===" << endl;
    
    vector<int> st;  // 用vector模拟栈
    
    // 入栈
    for(int i = 1; i <= 3; i++) {
        st.push_back(i);
        cout << "入栈: " << i << endl;
    }
    
    // 查看栈顶
    if(!st.empty()) {
        cout << "栈顶: " << st.back() << endl;
    }
    
    // 出栈
    while(!st.empty()) {
        cout << "出栈: " << st.back() << endl;
        st.pop_back();
    }
}

// 竞赛常见：括号匹配问题
bool isValidParenthesesContest(const string& s) {
    stack<char> st;
    
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if(st.empty()) return false;
            char top = st.top();
            if((c == ')' && top == '(') ||
               (c == ']' && top == '[') ||
               (c == '}' && top == '{')) {
                st.pop();
            } else {
                return false;
            }
        }
    }
    
    return st.empty();
}

// 竞赛常见：单调栈（找下一个更大元素）
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;  // 存储索引
    
    for(int i = 0; i < n; i++) {
        while(!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    
    return result;
}

// 竞赛常见：DFS非递归实现
void dfsIterative(const vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    stack<int> st;
    
    st.push(start);
    visited[start] = true;
    
    cout << "DFS遍历顺序: ";
    while(!st.empty()) {
        int node = st.top();
        st.pop();
        cout << node << " ";
        
        for(int neighbor : graph[node]) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                st.push(neighbor);
            }
        }
    }
    cout << endl;
}

int main() {
    // 传统栈演示
    stackSTLDemo();
    customStackDemo();
    
    // 竞赛常用写法
    stackContestDemo();
    vectorAsStackDemo();
    
    // 竞赛常见应用
    cout << "\n=== 竞赛常见应用 ===" << endl;
    
    // 括号匹配
    vector<string> testCases = {"()[]{}", "([)]", "((()))"};
    for(const string& test : testCases) {
        cout << "字符串 \"" << test << "\" 是否有效: " 
             << (isValidParenthesesContest(test) ? "是" : "否") << endl;
    }
    
    // 单调栈
    vector<int> nums = {2, 1, 2, 4, 3, 1};
    vector<int> nextGreater = nextGreaterElement(nums);
    cout << "数组: ";
    for(int x : nums) cout << x << " ";
    cout << endl;
    cout << "下一个更大元素: ";
    for(int x : nextGreater) cout << x << " ";
    cout << endl;
    
    // DFS非递归
    vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};
    dfsIterative(graph, 0);
    
    // 传统应用演示
    cout << "\n=== 传统应用演示 ===" << endl;
    isValidParentheses("()[]{}");
    isValidParentheses("([)]");
    isValidParentheses("((()))");
    evaluatePostfix("23+4*");
    evaluatePostfix("12+34-*");
    
    cout << "\n=== 竞赛选择指南 ===" << endl;
    cout << "1. 简单栈操作：使用 stack<T>" << endl;
    cout << "2. 需要访问中间元素：使用 vector<T>" << endl;
    cout << "3. 括号匹配：stack<char>" << endl;
    cout << "4. 单调栈：stack<int> 存储索引" << endl;
    cout << "5. DFS非递归：stack<int> 存储节点" << endl;
    
    return 0;
}
